/************************************************************************

								Heroes IV
					  Copyright 2001, The 3DO Company

	------------------------------------------------------------------
  						       circle_calculator.h

	$Header: $

	$NoKeywords: $

 ************************************************************************/

#ifndef CIRCLE_CALCULATOR_H_INCLUDED
#define CIRCLE_CALCULATOR_H_INCLUDED

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

#include <assert.h>
#include "elements_of.h"
#include "map_point.h"
#include "square.h"

// This class calculates all the points in a circle around a given map point, in order
// of increasing distance. 
class t_circle_calculator
{
	public:
		enum
		{
			k_max_offset = 102
		};

		// Start a sequence. The base class will return all points with 
		// offsets <= k_max_offset
		t_circle_calculator(const t_map_point_2d &center);

		// Get the next point in a sequence. Return false if we've found the end.
		// NOTE: NOT VIRTUAL for speed reasons.
		bool get_next_point(t_map_point_2d &next);

	protected:
		// The difference between two points. bigger >= smaller.
		struct t_offset
		{
			unsigned char bigger;
			unsigned char smaller;
		};

		// A list of offsets (differences between points), sorted in order
		// of increasing distance
		static const t_offset k_offsets[5356];

		const short m_stop_point; // Index in k_offsets to stop at

		t_map_point_2d m_center;
		const t_offset *m_cur_offset; // Current memeber of k_offsets
		t_map_point_2d m_points[8]; // Points for this offset
		int m_point_count; // Number of valid points in m_points;
		t_map_point_2d *m_cur_point; // Current pointer into m_points

		t_circle_calculator(const t_map_point_2d &center, short stop_point);
};

inline
t_circle_calculator::t_circle_calculator(const t_map_point_2d &center)
	: m_stop_point(ELEMENTS_OF(k_offsets)), m_center(center), m_cur_offset(k_offsets - 1), m_point_count(0), m_cur_point(m_points)
{
	assert(k_offsets[ELEMENTS_OF(k_offsets) - 1].smaller == k_max_offset);
	assert(k_offsets[ELEMENTS_OF(k_offsets) - 1].bigger == k_max_offset);
}

inline
t_circle_calculator::t_circle_calculator(const t_map_point_2d &center, short stop_point)
	: m_stop_point(stop_point), m_center(center), m_cur_offset(k_offsets - 1), m_point_count(0), m_cur_point(m_points)
{
	assert(k_offsets[ELEMENTS_OF(k_offsets) - 1].smaller == k_max_offset);
	assert(k_offsets[ELEMENTS_OF(k_offsets) - 1].bigger == k_max_offset);
}

inline
bool t_circle_calculator::get_next_point(t_map_point_2d &next)
{
	if (m_cur_point == m_points + m_point_count)
	{
		m_cur_offset++;
		
		if (m_cur_offset >= k_offsets + m_stop_point)
		{
			return false;
		}
		
		// Generate new m_points
		// Use all eight combinations of x +/- bigger, y +/- smaller and
		// x +/- smaller, y +/- bigger
		if (m_cur_offset->bigger == 0)
		{
			m_point_count = 1;
			m_points[0] = m_center;
		}
		else
		{
			m_points[0] = m_center + t_map_point_2d( m_cur_offset->bigger,   m_cur_offset->smaller);
			m_points[1] = m_center + t_map_point_2d(-m_cur_offset->bigger,   m_cur_offset->smaller);
			if (m_cur_offset->bigger != m_cur_offset->smaller)
			{
				m_points[2] = m_center + t_map_point_2d( m_cur_offset->smaller,  m_cur_offset->bigger);
				m_points[3] = m_center + t_map_point_2d( m_cur_offset->smaller, -m_cur_offset->bigger);	

				if (m_cur_offset->smaller == 0)
				{
					m_point_count = 4;
				}
				else
				{
					m_points[4] = m_center + t_map_point_2d( m_cur_offset->bigger,  -m_cur_offset->smaller);
					m_points[5] = m_center + t_map_point_2d(-m_cur_offset->bigger,  -m_cur_offset->smaller);
					m_points[6] = m_center + t_map_point_2d(-m_cur_offset->smaller,  m_cur_offset->bigger);
					m_points[7] = m_center + t_map_point_2d(-m_cur_offset->smaller, -m_cur_offset->bigger);
					m_point_count = 8;
				}
			}
			else
			{
				m_points[2] = m_center + t_map_point_2d( m_cur_offset->bigger,  -m_cur_offset->smaller);
				m_points[3] = m_center + t_map_point_2d(-m_cur_offset->bigger,  -m_cur_offset->smaller);
				m_point_count = 4;
			}
		}

		m_cur_point = m_points;
	}

	next = *m_cur_point;

	m_cur_point++;

	return true;
}


// Similar to t_circle_calculator, but limited to points in a circle in 
// between two diameters. 
class t_ring_calculator : public t_circle_calculator
{
	public:
		// Start a sequence. 
		t_ring_calculator(const t_map_point_2d &center, int inner_diameter, int outer_diameter);

	private:
		// Start points for the circle list. To get all the offsets for a ring
		// with a inner diameter d (where d is integral), start at
		// the k_start_points[d]'th entry of k_offsets
		static const short k_start_points[206];

		// Stop points for the circle list. To get all the offsets for a circle
		// of diameter d (where d is integral), look at
		// the first k_stop_points[d] entries of k_offsets
		static const short k_stop_points[206];
};

inline
t_ring_calculator::t_ring_calculator(const t_map_point_2d &center, int inner_diameter, int outer_diameter)
	: t_circle_calculator(center, k_stop_points[outer_diameter])
{
	assert(k_stop_points[ELEMENTS_OF(k_stop_points) - 1] != 0); // All data filled in
	assert(inner_diameter < ELEMENTS_OF(k_stop_points));
	assert(inner_diameter >= 0);
	assert(outer_diameter < ELEMENTS_OF(k_stop_points));
	assert(outer_diameter >= 0);
	assert(outer_diameter >= inner_diameter);

	m_cur_offset = k_offsets + k_start_points[inner_diameter] - 1;


	assert(m_cur_offset == k_offsets - 1 ||
		   sqrt((double)(square((int)(m_cur_offset->bigger)) + square((int)(m_cur_offset->smaller)))) < inner_diameter / 2.0);
	assert(sqrt((double)(square((int)((m_cur_offset + 1)->bigger)) + square((int)((m_cur_offset + 1)->smaller)))) >= inner_diameter / 2.0);
	assert(k_stop_points[outer_diameter] == 0 ||
		   sqrt((double)(square((int)(k_offsets[m_stop_point - 1].bigger)) + square((int)(k_offsets[m_stop_point - 1].smaller)))) <= outer_diameter / 2.0);
	assert(sqrt((double)(square((int)(k_offsets[m_stop_point].bigger)) + square((int)(k_offsets[m_stop_point].smaller)))) > outer_diameter / 2.0);
}


#endif // CIRCLE_CALCULATOR_H_INCLUDED
